package com.zjj.learn.algorithmPlus.segment1.binarySearch;

/**
 * 二分查找
 * <p>
 * leetcode 相关题目：704、35、34【leftmost 和 rightmost 的应用】
 *
 * @author zjj_admin
 */
public class BinarySearch {


    /**
     * @param a      递增数组 a
     * @param target 查找目标
     * @return 目标值在数组中的索引，不存在返回 -1
     */
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                //目标在左侧，需要将右指针指向当前索引前一个
                j = m - 1;
            } else if (a[m] < target) {
                //目标在右侧，需要将左指针指向当前索引后一个
                i = m + 1;
            } else {
                //找到了目标，返回索引
                return m;
            }
        }
        return -1;
    }


    /**
     * @param a      递增数组
     * @param target 需要查找的数据
     * @return
     */
    public static int binarySearchImprove(int[] a, int target) {
        int i = 0, j = a.length;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                //目标在左侧
                j = m;
            } else if (a[m] < target) {
                //目标在右侧，需要将左指针指向当前索引后一个
                i = m + 1;
            } else {
                //找到了目标，返回索引
                return m;
            }
        }
        return -1;
    }


    /**
     * 再次改动后的代码
     * 优点：目的是减少循环里面的代码执行条数，原来的代码里面有 if 和 else if，现在只有一个判断条件了
     * 缺点：最好的情况就不是 O(1) 了，而是 O(log(n)) 了，和最坏情况相同。
     *
     * @param a      递增数组
     * @param target 需要查找的数据
     * @return
     */
    public static int binarySearch3(int[] a, int target) {
        int i = 0, j = a.length;
        while (1 < j - i) {
            //计算中间索引
            int m = (i + j) >>> 1;
            //目标小于中间值，缩小有边界
            if (target < a[m]) {
                j = m;
            } else {
                //target == a[m] 或者 target > a[m]，就不能够是 i = m + 1 了
                i = m;
            }
        }
        if (a[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

    /**
     * 基础版本思考：
     * 1、为什么是  i <= j，而不是 i < j？
     *    当 i < j 时就只会比较 i 和 j 之间的数据，当 i <= j 时，i 和 j 最后所指向的元素也会参与比较。
     *
     * 2、(i + j) / 2 有没有问题？
     *    有问题，假设数组的数据非常多，就有可能会出现 i + j 超过了 int 类型正数范围，就出出现异常。
     *    同时，若没有超过正数的 32 位，但是首位变成 1 了时就成成为一个负数，因为在 Java 里面是将首位看做符号位的。
     *    怎么解决：使用无符号右移 >>> ，用 ( i + j ) >>> 1 表示 ( i + j ) / 2 ，两者是等价的。
     *
     * 3、写成小于符号 (<) 有什么优势？
     *    这个和数据是升序的有关系，会让代码理解更加容易，不信你可以试试写一个 a[m] > target 会不会没有 < 符号好理解。
     *
     *
     * 改进版本的思考：
     * 1、改进版本 中的 i 、 j 和 基础版本中有什么区别 ？
     *    i 的值没有改变，都是表示最左侧的索引，但是 j 的含义不一样；在基础版中 j 表示需要被比较的最右侧数据索引，而在改进版本中 j 表示的是右侧索引 + 1。
     *
     * 2、为什么在改进版中循环是使用 i < j 而不是 i <= j ？
     *    当数据不存在时有可能会出现死循环。
     *
     */

    /**
     * Java 中的二分查找代码
     * 分析最后没有找到时返回 return -(low + 1); 表示什么意思。
     * 实现一个功能，在一个数组中查找一个数据，若数组中不存在时，就将该数据插入到数组中去。
     * <p>
     * 新需求
     * 当一个数组中目标元素是重复的时，我们返回数组最左侧的目标索引。
     */


    /**
     * 二分查找返回最左侧索引
     *
     * @param a      升序数组，有重复元素
     * @param target 目标
     * @return 返回目标在数组中的最左侧索引，不存在就返回 -1
     */
    public static int binarySearchLeftmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                //找到了目标，不马上返回数据，将有右指针只想 m -1，然后继续循环即可
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }


    /**
     * 二分查找返回最右侧索引
     *
     * @param a      升序数组，有重复元素
     * @param target 目标
     * @return 返回目标在数组中的最右侧索引，不存在就返回 -1
     */
    public static int binarySearchRightmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                //找到了目标，不马上返回数据，将有左指针只想 m + 1，然后继续循环即可
                candidate = m;
                i = m + 1;
            }
        }
        return candidate;
    }

    /**
     * 上述代码中 返回的 -1 没有任何意义，可以适当改动一下
     */

    /**
     * 二分查找返回大于等于目标值的最左侧的索引
     *
     * @param a      升序数组，有重复元素
     * @param target 目标
     * @return 二分查找返回大于等于目标值的最左侧的索引
     */
    public static int binarySearchLeftmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target <= a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        //思考，返回的 i 什么意思
        return i;
    }


    /**
     * 返回小于等于 target 的最大索引
     *
     * @param a      升序数组，有重复元素
     * @param target 目标
     * @return 返回数组中 <= target 的最大索引
     */
    public static int binarySearchRightmost2(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        return i - 1;
    }


}
